package com.algorithm.dp;

import java.util.Arrays;

import static com.google.common.primitives.Ints.max;

public class LongestCommonSubString {
    public static void main(String[] args) {
        String str1 = "abcdefjklpp";
        String str2 = "abhjklopp";
        int l = calcLcs00(str1, str2);
        System.out.println(l);
        l = calcLcs01(str1, str2);
        System.out.println(l);
        l = calcLcs02(str1, str2);
        System.out.println(l);
    }

    /**
     * 最长公共子串状态转移方程:dp[i][j] = max{dp[i-1][j],dp[i][j-1],s[i][j]} s[i][j]表示当str1的第i位和str2第j位相同时,依次前推的最大长度
     *
     * @param str1
     * @param str2
     * @return
     */
    private static int calcLcs00(String str1, String str2) {
        Integer[][] dp = new Integer[str1.length()][str2.length()];

        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = str1.contains(str2.substring(0, 1)) ? 1 : 0;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = str2.contains(str1.substring(0, 1)) ? 1 : 0;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                String left1 = str1.substring(0, i);
                String left2 = str2.substring(0, j);
                String end1 = left1.substring(left1.length() - 1);
                String end2 = left2.substring(left2.length() - 1);
                int maxLengthWithLast1;
                if (end1.equals(end2)) {
                    maxLengthWithLast1 = calcWithLastCommonLength(left1, left2);
                } else {
                    maxLengthWithLast1 = 0;
                }
                dp[i][j] = max(maxLengthWithLast1, dp[i][j - 1], dp[i - 1][j]);
            }
        }
        /*for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }*/

        return dp[dp.length - 1][dp[0].length - 1];
    }

    private static int calcWithLastCommonLength(String left1, String left2) {
        int i = left1.length() - 1;
        int j = left2.length() - 1;
        int count = 0;
        while (i >= 0 && j >= 0 && left1.charAt(i--) == left2.charAt(j--)) {
            count++;
        }
        return count;
    }

    /**
     * 思考:参考背包问题,是否可以将dp优化为一维数组?
     * 能使用一维数组代替二维数组的情况必须满足的条件:本次最优解依赖于子问题的最优解
     *
     * @param str1
     * @param str2
     * @return
     */
    private static int calcLcs01(String str1, String str2) {
        Integer[] dp = new Integer[str1.length()];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = str1.substring(str1.length() - 1).equals(str2.substring(str2.length() - 1)) ? 1 : 0;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = str2.length() - 1; j >= 0; j--) {
                String left1 = str1.substring(0, i + 1);
                String left2 = str2.substring(0, j + 1);
                String end1 = left1.substring(left1.length() - 1);
                String end2 = left2.substring(left2.length() - 1);
                int maxLengthWithLast1;
                if (end1.equals(end2)) {
                    maxLengthWithLast1 = calcWithLastCommonLength(left1, left2);
                } else {
                    maxLengthWithLast1 = 0;
                }
                dp[i] = max(maxLengthWithLast1, dp[i], dp[i - 1]);
            }
        }
        return dp[dp.length - 1];
    }

    /**
     * 另一种相似思想,dp[i][j]保存的是从结尾开始往前扫描的最长连续子串,
     * 这样dp[i][j] = (dp[i]==dp[j])?(dp[i-1][j-1])+1:0
     * 此时需要扫描dp(或额外加一个maxLength参数记录)才能得到最长子串长度
     * 因为当前问题最优解只与前一个问题最优解有关,所以可以考虑使用滚动数组的思想解决此问题,也可以考虑使用一维数组解决此问题
     * 两行滚动数组:每次写其中一行数据时都会使用前一行数据,当前行写完之后上一行也没用了,所以使用前一行作为下一行继续写数据
     * 【与一维数组相比，滚动数组更好理解，但也有限制条件：只有在明确当前问题最优解与哪几个子问题相关时才可以使用，因为前面的数据最终会被覆盖掉】
     */
    public static int calcLcs02(String str1, String str2) {
        Integer[][] dp = new Integer[2][str2.length()];
        int maxLength = 0;
        Integer now = 1;
        Integer pre = 0;

        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                String left1 = str1.substring(0, i + 1);
                String left2 = str2.substring(0, j + 1);
                String end1 = left1.substring(left1.length() - 1);
                String end2 = left2.substring(left2.length() - 1);
                if (i == 0) {
                    dp[now][j] = end1.equals(end2) ? 1 : 0;
                    dp[pre][j] = 0;
                    continue;
                }
                if (j == 0) {
                    dp[now][j] = end1.equals(end2) ? 1 : 0;
                    continue;
                }
                dp[now][j] = end1.equals(end2) ? dp[pre][j - 1] + 1 : 0;
                if (dp[now][j] > maxLength) {
                    maxLength = dp[now][j];
                }
            }
            System.out.println(Arrays.toString(dp[now]));
            Integer temp = now;
            now = pre;
            pre = temp;
        }

        return maxLength;
    }


    /**
     *
     *
     */
    public static int calcLcs03(String str1, String str2) {
        return 0;
    }
}
